//n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 
//
// 
// 
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 4
//输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
//解释：如上图所示，4 皇后问题存在两个不同的解法。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：[["Q"]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。 
// 
// 
// 
// Related Topics 数组 回溯 
// 👍 930 👎 0


package service.week03.leetcode.editor.cn;

import java.util.*;

//Java：N 皇后
public class P51NQueens {
    public static void main(String[] args) {
        Solution solution = new P51NQueens().new Solution();
        // TO TEST
        solution.solveNQueens(4);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        private Map<Integer,Boolean> usedIplusJ=new HashMap<>();
        private Map<Integer,Boolean> usedIminusJ=new HashMap<>();
        /**
         * 全排列+dfs
         *
         * @param n
         * @return
         */
        public List<List<String>> solveNQueens(int n) {
            int[] nums=new int[n];
            for (int i = 0; i < n; i++) {
                nums[i]=i;
            }
            Deque<Integer> deque=new ArrayDeque<>();
            List<List<Integer>> tempRes=new ArrayList<>();
            List<List<String>> res=new ArrayList<>();
            help(0,nums,deque,tempRes);
            for (List<Integer> t:tempRes){
                List<String> temp=new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    char[] row = new char[n];
                    Arrays.fill(row, '.');
                    row[t.get(i)] = 'Q';
                    temp.add(new String(row));
                }
                res.add(temp);
            }

            return res;
        }

        public void help(int row, int[] nums, Deque<Integer> deque, List<List<Integer>> res) {

            //递归终止条件
            if (deque.size() == nums.length) {
                res.add(new ArrayList<>(deque));
                return;
            }

            for (int i = 0; i < nums.length; i++) {
                if (deque.contains(nums[i])) {
                    continue;
                }
                //对角线
                if(usedIplusJ.containsKey(row+i) && usedIplusJ.get(row+i)){
                    continue;
                }
                if(usedIminusJ.containsKey(row-i) && usedIminusJ.get(row-i)){
                    continue;
                }
                usedIplusJ.put(row+i,true);
                usedIminusJ.put(row-i,true);
                deque.addLast(nums[i]);
                help(row + 1, nums, deque, res);
                usedIplusJ.put(row+i,false);
                usedIminusJ.put(row-i,false);
                deque.removeLast();
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}